package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/19 16:28
 * @description: TODO
 */
public class _065_旅行商问题 {


    @Test
    public void test1() {

        int[][] graph = {
                {0, 10, 15, 20, 25},
                {10, 0, 35, 25, 30},
                {15, 35, 0, 30, 30},
                {20, 25, 30, 0, 10},
                {25, 30, 30, 10, 0}
        };
        int tsp = tsp(graph, 0);
        System.out.println(tsp);

    }
    /**
     * 解题的思路是, 先走一个节点,然后遍历剩余节点的集合(此剩余节点不包括之前走过的所有节点),当剩余节点为空时,返回当前节点到初始节点的距离
     * 在遍历剩余集合时递归调用,寻找最小值,获得最小的距离
     * 不可避免会有重复的路径,所以可以一个表记录走过的路程,以免重复计算.
     */

    /**
     * 递归求解
     *
     * @param graph
     * @param start
     * @return
     */
    public int tsp(int[][] graph, int start) {

        int end[] = new int[graph.length - 1];
        int index = 0;
        for (int i = 0; i < graph.length; i++) {
            if (i != start) {
                end[index++] = i;
            }
        }
        int min = digui(graph, start, start, end);
        return min;
    }

    private int digui(int[][] graph, int firstIndex, int start, int[] end) {
        if (end.length == 0) {
            return graph[start][firstIndex];
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < end.length; i++) {
            // 拷贝一个数组
            int newEnd[] = new int[end.length - 1];
            int index = 0;
            for (int i1 = 0; i1 < end.length; i1++) {
                if (end[i1] != end[i]) {
                    newEnd[index++] = end[i1];
                }
            }
            int temp = digui(graph, firstIndex, end[i], newEnd);
            System.out.println(start + " " + end[i] + " " + Arrays.toString(end) + " " + temp);
            min = Math.min(min, graph[start][end[i]] + temp);
        }
        return min;
    }

}
